Tetration (bị giới hạn ở N 2 {\displaystyle \mathbb {N} ^{2}} ) không phải là một hàm đệ quy nguyên thuỷ. Người ta có thể chứng minh bằng cảm ứng rằng với mọi hàm đệ quy sơ cấp f, có một hằng số c sao cho

f ( x ) ≤ 2 2 ⋅ ⋅ x ⏟ c . {\displaystyle f(x)\leq \underbrace {2^{2^{\cdot ^{\cdot ^{x}}}}} _{c}.}

Chúng ta biểu thị phía bên tay phải bởi g ( c , x ) {\displaystyle g(c,x)} . Giả sử ngược lại rằng tetration là đệ quy sơ cấp. g ( x , x ) + 1 {\displaystyle g(x,x)+1} cũng là đệ quy sơ cấp. Theo bất đẳng thức trên, có một hằng số c sao cho g ( x , x ) + 1 ≤ g ( c , x ) {\displaystyle g(x,x)+1\leq g(c,x)} . Bằng cách để x = c {\displaystyle x=c} , chúng ta có g ( c , c ) + 1 ≤ g ( c , c ) {\displaystyle g(c,c)+1\leq g(c,c)} , một mâu thuẫn.